C. 取石子遊戲 (kgame)

一開始有 N 顆石頭與一個正整數 K,有兩個人會輪流取出一些石頭。

假設遊戲進行了 m 輪,並且取出的石頭數量的序列為 a1,a2,,am,那麼必須要滿足以下兩個條件:

先將石頭取完的那個人獲勝,若是雙方都無法將石頭取完即視為平手。

在已知 NK 的情況下,請問誰有必勝策略?

在一筆測資中,你需要處理 T 組輸入。

子任務分數額外輸入限制
15T 組輸入中的 N 的總和 500
295無額外限制。

Example

input
output

Note

在範例的第一筆輸入中,小紅可以選擇先拿走 22 顆石頭,這樣下一輪小葉只能拿 11 顆石頭,最後小紅可以再把剩下 22 顆石頭拿走,獲得勝利。